package leetcode算法面试题.字符串;

import java.util.List;

public class 单词拆分Ⅱ {
    class Solution{
        public boolean wordBreak(String s, List<String> wordDict){
            boolean[] valid = new boolean[s.length() + 1];
            valid[0] = true;
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 0; j < i; j++) {
                    //String的substring方法从j开始到i结束 不包括i
                  if (wordDict.contains(s.substring(j,i)) && valid[j]){
                      valid[i] = true;
                  }
                }
            }
                 return valid[s.length()];
        }
    }
}
